package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class LC802 {
    
    HashSet<Integer> safeNodeSet = new HashSet<>();
    HashSet<Integer> unsafeNodeSet = new HashSet<>();


    boolean dfs(int[][] graph,boolean[] visited, int node) {
        if (unsafeNodeSet.contains(node)) return false;
        if (safeNodeSet.contains(node)) return true;
        visited[node] = true;

        for (int i = 0; i < graph[node].length; i++) {
            if (safeNodeSet.contains(graph[node][i])) continue;
            if (unsafeNodeSet.contains(graph[node][i])) {
                unsafeNodeSet.add(i);
                return false;
            }
            if (graph[node][i] == node) {
                unsafeNodeSet.add(node);
                return false;
            }
            if (visited[graph[node][i]]) {
                unsafeNodeSet.add(graph[node][i]);
                unsafeNodeSet.add(node);
                return false;
            }
            boolean res = dfs(graph,visited,graph[node][i]);
            if (!res) {
                unsafeNodeSet.add(node);
                return false;
            }
            else if( i == graph[node].length - 1) {
                safeNodeSet.add(node);
                visited[node] = false;
                return true;
            }
        }
        visited[node] = false;
        return true;
    }

    public  List<Integer> eventualSafeNodes(int[][] graph) {
        for (int i = 0; i < graph.length; i++) {
            if (graph[i].length == 1 && graph[i][0] == i) {
                unsafeNodeSet.add(i);
                continue;
            }
            boolean isSafe = true;
            for (int j = 0; j < graph[i].length; j++) {
                if (graph[i][j] != i) {
                    isSafe = false;
                    break;
                }
            }
            if (isSafe) safeNodeSet.add(i);
        }
        if (safeNodeSet.size() == 0) return new ArrayList<Integer>();

        boolean[] visited = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++) {
            Arrays.fill(visited,false);
            if (dfs(graph,visited,i))
                safeNodeSet.add(i);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) {
            if (safeNodeSet.contains(i))
                ans.add(i);
        }
        return ans;
        
    }

    public static void main(String[] args) {
        LC802 lc802 = new LC802();

        int[][] g =  {{},{0,2,3,4},{3},{4},{}};
        lc802.eventualSafeNodes(g);
    }

}
